package leetcode.力扣竞赛.第333场周赛;

/**
 * @author: yan
 * @description: 将整数减少到零需要的最少操作数
 * @create: 2023-02-22 14:08
 **/

/**
 * tips : x & -x 会得到最低位的值，2的幂会得到本身
 * 可以利用这个tip去判断某个数是否是2的幂
 */
public class Solution2571 {

    public static void main(String[] args) {
        System.out.println(minOperations(54));
    }

    public static int minOperations(int n) {
        return dfs(n);
    }

    private static int dfs(int x) {
        int lowbit = lowbit(x);
        if (lowbit == x) return 1;
        return Math.min(dfs(x+lowbit) + 1, dfs(x-lowbit) + 1);
    }

    private static int lowbit(int x){
        return x & -x;
    }

}
